package 设计链表;


class ListNode {
    int val;
    ListNode prev, next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(ListNode next, ListNode prev, int val) {
        this.next = next;
        this.prev = prev;
        this.val = val;
    }
}


public class MyLinkedList2 {

    int size;
    ListNode head;  // 虚拟头节点
    ListNode tail;  // 虚拟尾节点

    // 初始化 MyLinkedList 对象
    public MyLinkedList2() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        // 不进行这一步，再加入节点的时候就会出现空指针异常
        head.next = tail;
        tail.prev = head;
    }

    // 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
    public int get(int index) {
        // index 认为是从1开始的数
        ListNode p = head.next;
        for (int i = 1; i <= index; i++) {
            if (p.next == head)
                return -1;
            p = p.next;
        }
        return p.val;
    }

    // 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点
    public void addAtHead(int val) {
        // 将节点指向虚拟头节点和以前的第一个节点
        ListNode insertFirstNode = new ListNode(head.next, head, val);
        // 将以前的第一个节点的前驱指向新节点
        head.next.prev = insertFirstNode;
        // 将虚拟头节点指向新的第一个节点
        head.next = insertFirstNode;
    }

    //  将一个值为 val 的节点追加到链表中作为链表的最后一个元素
    public void addAtTail(int val) {
        // 将节点指向虚拟尾节点和以前的最后一个节点
        ListNode insertLastNode = new ListNode(tail, tail.prev, val);
        // 将以前的最后一个节点的后驱指向新节点
        tail.prev.next = insertLastNode;
        // 将虚拟尾节点的前驱指向新节点
        tail.prev = insertLastNode;

    }

    // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾
    // 如果 index 比长度更大，该节点将 不会插入 到链表中
    public void addAtIndex(int index, int val) {
        if ( index == 0 )
            return;
        // 工作指针，寻找下标为 index 的节点位置
        ListNode p = head;
        for (int i = 0; i < index; i++) {
            if (p.next == null)
                return;
            p = p.next;
        }
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾
        if (p == tail) {
            addAtTail(val);
        } else {
            // 新节点的前指针和后指针加入到链表中
            ListNode insertNode = new ListNode(p, p.prev, val);
            // 原链表中 index - 1 节点的后指针指向新节点
            p.prev.next = insertNode;
            // 原链表 index 节点的前指针指向新节点
            p.prev = insertNode;
        }
    }

    // 如果下标有效，则删除链表中下标为 index 的节点
    public void deleteAtIndex(int index) {
        if ( index == 0 )
            return;
        // 工作指针，寻找下标为 index 的节点位置
        ListNode p = head;
        for (int i = 0; i < index; i++) {
            if (p.next == null)
                return;
            p = p.next;
        }
        // 将 p 的前驱节点的后指针指向 p 的后驱节点
        p.prev.next = p.next;
        // 将 p 的后驱节点的前指针指向 p 的前驱节点
        p.next.prev = p.prev;
    }

    public void PrintList() {
        ListNode p = head.next;
        while (p != tail) {
            System.out.print(p.val + ",");
            p = p.next;
        }
        System.out.println();
    }

}
